⟸ pàgina anterior ⟸

Exercici 3 (Tasca 6).

(R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE)

Classificació III: domini de les funcions computables

Per a cadascun dels llenguatges L següents, decidiu si L \in \mathbf{R}, L \in \mathbf{RE} \setminus \mathbf{R}, L \in \mathbf{coRE} \setminus \mathbf{R} o L \notin \mathbf{RE} \cup \mathbf{coRE}.

1. \{p \mid |\mathrm{Dom}(\varphi_p)| \geq 0\}
   
2. \{p \mid |\mathrm{Dom}(\varphi_p)| \geq 10\} (resoldre aquest exercici de RACSO pot donar algunes pistes)
   
3. \{p \mid \mathrm{Dom}(\varphi_p) \subseteq 2\mathbb N\}
   
4. \{p \mid \mathrm{Dom}(\varphi_p) \supseteq 2\mathbb N\}
   
5. \{p \mid \exists y\ \mathrm{Dom}(\varphi_p) \subseteq \mathrm{Dom}(\varphi_y)\}
   
6. \{p \mid \exists y\ \mathrm{Dom}(\varphi_p) \supseteq \mathrm{Dom}(\varphi_y)\}
   
7. \{p \mid \mathrm{Dom}(\varphi_p) \in \mathbf{R}\}
   
8. \{p \mid \mathrm{Dom}(\varphi_p) \notin \mathbf{R}\}
   
9. \{p \mid \mathrm{Dom}(\varphi_p) \in \mathbf{RE}\}
   
10. \{p \mid \mathrm{Dom}(\varphi_p) \notin \mathbf{RE}\}
    
11. \{p \mid p \leq 100 \land \mathrm{Dom}(\varphi_p) \in \mathbf{R}\}
    
12. \{p \mid p \leq 100 \land \mathrm{Dom}(\varphi_p) \in \mathbf{RE}\}